{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Please input the size of population: \n",
      "Please input the size of Crossover Rate: \n",
      "Please input the size of Mutation Rate: \n",
      "Please input the mutation selection rate: \n",
      "Please input number of iteration: \n",
      "[[3, 0, 5, 3, 8, 9, 7, 5, 1, 8, 4, 3, 4, 9, 0, 4, 7, 3, 5, 8, 3, 8, 5, 6, 9, 4, 0, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 6, 5, 0, 1, 7, 6, 2, 4, 0, 9, 7, 9, 1, 4, 8, 9, 1, 5, 2, 8, 5, 2, 4, 6, 6, 3, 1, 1, 1, 7, 6, 7, 5, 5, 9, 2, 2, 8, 7, 6, 3, 9, 1, 2, 1, 2, 4, 9, 6, 3, 7, 0, 0, 2, 1], [9, 5, 5, 0, 6, 1, 3, 7, 4, 5, 4, 5, 4, 9, 1, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 7, 4, 3, 1, 9, 5, 4, 6, 0, 5, 0, 8, 7, 2, 1, 9, 9, 6, 1, 2, 7, 8, 0, 6, 3, 9, 1, 2, 7, 2, 3, 2, 1, 7, 3, 2, 2, 7, 3], [9, 5, 5, 0, 6, 1, 3, 7, 4, 5, 4, 5, 4, 9, 1, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 7, 4, 3, 1, 9, 5, 4, 6, 0, 5, 0, 8, 7, 2, 1, 9, 9, 6, 1, 2, 7, 8, 0, 6, 3, 9, 1, 2, 7, 2, 3, 2, 1, 7, 3, 2, 2, 7, 3], [3, 0, 5, 3, 8, 9, 7, 5, 1, 8, 4, 3, 4, 9, 0, 4, 7, 3, 5, 8, 3, 8, 5, 6, 9, 4, 0, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 6, 5, 0, 1, 7, 6, 2, 4, 0, 9, 7, 9, 1, 4, 8, 9, 1, 5, 2, 8, 5, 2, 4, 6, 6, 3, 1, 1, 1, 7, 6, 7, 5, 5, 9, 2, 2, 8, 7, 6, 3, 9, 1, 2, 1, 2, 4, 9, 6, 3, 7, 0, 0, 2, 1], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3], [6, 5, 1, 1, 6, 1, 7, 9, 5, 8, 3, 5, 4, 9, 3, 4, 6, 1, 5, 8, 3, 8, 5, 6, 9, 4, 4, 4, 3, 9, 3, 0, 4, 8, 5, 0, 6, 6, 8, 7, 2, 7, 2, 0, 8, 8, 6, 0, 1, 0, 9, 2, 1, 8, 3, 9, 6, 8, 0, 5, 7, 6, 4, 3, 1, 9, 5, 4, 9, 0, 2, 0, 8, 7, 2, 3, 9, 5, 7, 1, 2, 7, 4, 0, 0, 4, 9, 1, 6, 7, 2, 3, 2, 5, 7, 1, 2, 2, 7, 3]]\n",
      "[[8899.0, 1088], [5059.3, 1228], [5059.3, 1228], [8899.0, 1088], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194], [7528.0, 1194]]\n",
      "the elapsed time:25.96403408050537\n"
     ]
    }
   ],
   "source": [
    "# -*- coding: utf-8 -*-\n",
    "\"\"\"\n",
    "Created on Thu May 24 13:32:33 2018\n",
    "\n",
    "@author: cheng-man wu\n",
    "\n",
    "LinkedIn: www.linkedin.com/in/chengmanwu\n",
    "Github: https://github.com/wurmen\n",
    "\"\"\"\n",
    "'''==========Solving job shop scheduling problem by NSGA-II algorithm in python======='''\n",
    "# importing required modules\n",
    "#import os\n",
    "import pandas as pd\n",
    "import numpy as np\n",
    "import time\n",
    "import copy\n",
    "''' ================= initialization setting ======================'''\n",
    "num_job=10 # number of jobs\n",
    "num_mc=10 # number of machines\n",
    "\n",
    "pt_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Processing Time\",index_col =[0])\n",
    "ms_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Machines Sequence\",index_col =[0])\n",
    "job_priority_duedate_tmp=pd.read_excel(\"JSP_dataset.xlsx\",sheet_name=\"Priority and Due date\",index_col =[0])\n",
    "\n",
    "# raw_input is used in python 2\n",
    "population_size=int(input('Please input the size of population: ') or 20) # default value is 20\n",
    "crossover_rate=float(input('Please input the size of Crossover Rate: ') or 0.8) # default value is 0.8\n",
    "mutation_rate=float(input('Please input the size of Mutation Rate: ') or 0.3) # default value is 0.3\n",
    "mutation_selection_rate=float(input('Please input the mutation selection rate: ') or 0.4)\n",
    "num_mutation_jobs=round(num_job*num_mc*mutation_selection_rate)\n",
    "num_iteration=int(input('Please input number of iteration: ') or 1000) # default value is 1000\n",
    "\n",
    "# speed up the data search\n",
    "# Below code can also be  written \"pt = pt_tmp.as_matrix().tolist()\"\n",
    "pt=[list(map(int, pt_tmp.iloc[i])) for i in range(num_job)]\n",
    "ms=[list(map(int,ms_tmp.iloc[i])) for i in range(num_job)]\n",
    "job_priority_duedate=[list(job_priority_duedate_tmp.iloc[i]) for i in range(num_job)]\n",
    "start_time = time.time()\n",
    "'''===========function==============='''\n",
    "'''-------non-dominated sorting function-------'''      \n",
    "def non_dominated_sorting(population_size,chroms_obj_record):\n",
    "    s,n={},{}\n",
    "    front,rank={},{}\n",
    "    front[0]=[]     \n",
    "    for p in range(population_size*2):\n",
    "        s[p]=[]\n",
    "        n[p]=0\n",
    "        for q in range(population_size*2):\n",
    "            \n",
    "            if ((chroms_obj_record[p][0]<chroms_obj_record[q][0] and chroms_obj_record[p][1]<chroms_obj_record[q][1]) or (chroms_obj_record[p][0]<=chroms_obj_record[q][0] and chroms_obj_record[p][1]<chroms_obj_record[q][1])\n",
    "            or (chroms_obj_record[p][0]<chroms_obj_record[q][0] and chroms_obj_record[p][1]<=chroms_obj_record[q][1])):\n",
    "                if q not in s[p]:\n",
    "                    s[p].append(q)\n",
    "            elif ((chroms_obj_record[p][0]>chroms_obj_record[q][0] and chroms_obj_record[p][1]>chroms_obj_record[q][1]) or (chroms_obj_record[p][0]>=chroms_obj_record[q][0] and chroms_obj_record[p][1]>chroms_obj_record[q][1])\n",
    "            or (chroms_obj_record[p][0]>chroms_obj_record[q][0] and chroms_obj_record[p][1]>=chroms_obj_record[q][1])):\n",
    "                n[p]=n[p]+1\n",
    "        if n[p]==0:\n",
    "            rank[p]=0\n",
    "            if p not in front[0]:\n",
    "                front[0].append(p)\n",
    "    \n",
    "    i=0\n",
    "    while (front[i]!=[]):\n",
    "        Q=[]\n",
    "        for p in front[i]:\n",
    "            for q in s[p]:\n",
    "                n[q]=n[q]-1\n",
    "                if n[q]==0:\n",
    "                    rank[q]=i+1\n",
    "                    if q not in Q:\n",
    "                        Q.append(q)\n",
    "        i=i+1\n",
    "        front[i]=Q\n",
    "                \n",
    "    del front[len(front)-1]\n",
    "    return front\n",
    "\n",
    "'''--------calculate crowding distance function---------'''\n",
    "def calculate_crowding_distance(front,chroms_obj_record):\n",
    "    \n",
    "    distance={m:0 for m in front}\n",
    "    for o in range(2):\n",
    "        obj={m:chroms_obj_record[m][o] for m in front}\n",
    "        sorted_keys=sorted(obj, key=obj.get)\n",
    "        distance[sorted_keys[0]]=distance[sorted_keys[len(front)-1]]=999999999999\n",
    "        for i in range(1,len(front)-1):\n",
    "            if len(set(obj.values()))==1:\n",
    "                distance[sorted_keys[i]]=distance[sorted_keys[i]]\n",
    "            else:\n",
    "                distance[sorted_keys[i]]=distance[sorted_keys[i]]+(obj[sorted_keys[i+1]]-obj[sorted_keys[i-1]])/(obj[sorted_keys[len(front)-1]]-obj[sorted_keys[0]])\n",
    "            \n",
    "    return distance            \n",
    "'''----------selection----------'''\n",
    "def selection(population_size,front,chroms_obj_record,total_chromosome):   \n",
    "    N=0\n",
    "    new_pop=[]\n",
    "    while N < population_size:\n",
    "        for i in range(len(front)):\n",
    "            N=N+len(front[i])\n",
    "            if N > population_size:\n",
    "                distance=calculate_crowding_distance(front[i],chroms_obj_record)\n",
    "                sorted_cdf=sorted(distance, key=distance.get)\n",
    "                sorted_cdf.reverse()\n",
    "                for j in sorted_cdf:\n",
    "                    if len(new_pop)==population_size:\n",
    "                        break                \n",
    "                    new_pop.append(j)              \n",
    "                break\n",
    "            else:\n",
    "                new_pop.extend(front[i])\n",
    "    \n",
    "    population_list=[]\n",
    "    for n in new_pop:\n",
    "        population_list.append(total_chromosome[n])\n",
    "    \n",
    "    return population_list,new_pop\n",
    "\n",
    "\n",
    "'''==================== main code ==============================='''\n",
    "'''----- generate initial population -----'''\n",
    "best_list,best_obj=[],[]\n",
    "population_list=[]\n",
    "for i in range(population_size):\n",
    "    nxm_random_num=list(np.random.permutation(num_job*num_mc)) # generate a random permutation of 0 to num_job*num_mc-1\n",
    "    population_list.append(nxm_random_num) # add to the population_list\n",
    "    for j in range(num_job*num_mc):\n",
    "        population_list[i][j]=population_list[i][j]%num_job # convert to job number format, every job appears m times\n",
    "        \n",
    "for n in range(num_iteration):           \n",
    "    '''-------- two point crossover --------'''\n",
    "    parent_list=copy.deepcopy(population_list)\n",
    "    offspring_list=[]\n",
    "    S=list(np.random.permutation(population_size)) # generate a random sequence to select the parent chromosome to crossover\n",
    "    \n",
    "    for m in range(int(population_size/2)):\n",
    "        \n",
    "        parent_1= population_list[S[2*m]][:]\n",
    "        parent_2= population_list[S[2*m+1]][:]\n",
    "        child_1=parent_1[:]\n",
    "        child_2=parent_2[:]\n",
    "        \n",
    "        cutpoint=list(np.random.choice(num_job*num_mc, 2, replace=False))\n",
    "        cutpoint.sort()\n",
    "    \n",
    "        child_1[cutpoint[0]:cutpoint[1]]=parent_2[cutpoint[0]:cutpoint[1]]\n",
    "        child_2[cutpoint[0]:cutpoint[1]]=parent_1[cutpoint[0]:cutpoint[1]]\n",
    "        \n",
    "        offspring_list.extend((child_1,child_2)) # append child chromosome to offspring list\n",
    "    '''----------repairment-------------'''\n",
    "    for m in range(population_size):\n",
    "        job_count={}\n",
    "        larger,less=[],[] # 'larger' record jobs appear in the chromosome more than m times, and 'less' records less than m times.\n",
    "        for i in range(num_job):\n",
    "            if i in offspring_list[m]:\n",
    "                count=offspring_list[m].count(i)\n",
    "                pos=offspring_list[m].index(i)\n",
    "                job_count[i]=[count,pos] # store the above two values to the job_count dictionary\n",
    "            else:\n",
    "                count=0\n",
    "                job_count[i]=[count,0]\n",
    "            if count>num_mc:\n",
    "                larger.append(i)\n",
    "            elif count<num_mc:\n",
    "                less.append(i)\n",
    "                \n",
    "        for k in range(len(larger)):\n",
    "            chg_job=larger[k]\n",
    "            while job_count[chg_job][0]>num_mc:\n",
    "                for d in range(len(less)):\n",
    "                    if job_count[less[d]][0]<num_mc:                    \n",
    "                        offspring_list[m][job_count[chg_job][1]]=less[d]\n",
    "                        job_count[chg_job][1]=offspring_list[m].index(chg_job)\n",
    "                        job_count[chg_job][0]=job_count[chg_job][0]-1\n",
    "                        job_count[less[d]][0]=job_count[less[d]][0]+1                    \n",
    "                    if job_count[chg_job][0]==num_mc:\n",
    "                        break        \n",
    "    \n",
    "    '''--------mutatuon--------'''   \n",
    "    for m in range(len(offspring_list)):\n",
    "        mutation_prob=np.random.rand()\n",
    "        if mutation_rate <= mutation_prob:\n",
    "            m_chg=list(np.random.choice(num_job*num_mc, num_mutation_jobs, replace=False)) # chooses the position to mutation\n",
    "            t_value_last=offspring_list[m][m_chg[0]] # save the value which is on the first mutation position\n",
    "            for i in range(num_mutation_jobs-1):\n",
    "                offspring_list[m][m_chg[i]]=offspring_list[m][m_chg[i+1]] # displacement\n",
    "            \n",
    "            offspring_list[m][m_chg[num_mutation_jobs-1]]=t_value_last # move the value of the first mutation position to the last mutation position   \n",
    "                        \n",
    "    \n",
    "    '''--------fitness value(calculate  makespan and TWET)-------------'''\n",
    "    total_chromosome=copy.deepcopy(parent_list)+copy.deepcopy(offspring_list) # combine parent and offspring chromosomes\n",
    "    chroms_obj_record={} # record each chromosome objective values as chromosome_obj_record={chromosome:[TWET,makespan]}\n",
    "    for m in range(population_size*2):\n",
    "        j_keys=[j for j in range(num_job)]\n",
    "        key_count={key:0 for key in j_keys}\n",
    "        j_count={key:0 for key in j_keys}\n",
    "        m_keys=[j+1 for j in range(num_mc)]\n",
    "        m_count={key:0 for key in m_keys}\n",
    "        d_record={} # record jobs earliness and tardiness time as d_record={job:[earliness time,tardiness time]}\n",
    "        \n",
    "        for i in total_chromosome[m]:\n",
    "            gen_t=int(pt[i][key_count[i]])\n",
    "            gen_m=int(ms[i][key_count[i]])\n",
    "            j_count[i]=j_count[i]+gen_t\n",
    "            m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "            \n",
    "            if m_count[gen_m]<j_count[i]:\n",
    "                m_count[gen_m]=j_count[i]\n",
    "            elif m_count[gen_m]>j_count[i]:\n",
    "                j_count[i]=m_count[gen_m]\n",
    "            \n",
    "            key_count[i]=key_count[i]+1\n",
    "    \n",
    "        for j in j_keys:\n",
    "            if j_count[j]>job_priority_duedate[j][1]:\n",
    "                job_tardiness=j_count[j]-job_priority_duedate[j][1]\n",
    "                job_earliness=0\n",
    "                d_record[j]=[job_earliness,job_tardiness]\n",
    "            elif j_count[j]<job_priority_duedate[j][1]:\n",
    "                job_tardiness=0\n",
    "                job_earliness=job_priority_duedate[j][1]-j_count[j]\n",
    "                d_record[j]=[job_earliness,job_tardiness]\n",
    "            else:\n",
    "                job_tardiness=0\n",
    "                job_earliness=0\n",
    "                d_record[j]=[job_earliness,job_tardiness]\n",
    "        \n",
    "        twet=sum((1/job_priority_duedate[j][0])*d_record[j][0]+job_priority_duedate[j][0]*d_record[j][1] for j in j_keys)\n",
    "        makespan=max(j_count.values())\n",
    "        chroms_obj_record[m]=[twet,makespan]\n",
    "                       \n",
    "    \n",
    "    '''-------non-dominated sorting-------'''      \n",
    "    front=non_dominated_sorting(population_size,chroms_obj_record)\n",
    "        \n",
    "    '''----------selection----------'''\n",
    "    population_list,new_pop=selection(population_size,front,chroms_obj_record,total_chromosome)\n",
    "    new_pop_obj=[chroms_obj_record[k] for k in new_pop]    \n",
    "    \n",
    "\n",
    "    '''----------comparison----------'''\n",
    "    if n==0:\n",
    "        best_list=copy.deepcopy(population_list)\n",
    "        best_obj=copy.deepcopy(new_pop_obj)\n",
    "    else:            \n",
    "        total_list=copy.deepcopy(population_list)+copy.deepcopy(best_list)\n",
    "        total_obj=copy.deepcopy(new_pop_obj)+copy.deepcopy(best_obj)\n",
    "        \n",
    "        now_best_front=non_dominated_sorting(population_size,total_obj)\n",
    "        best_list,best_pop=selection(population_size,now_best_front,total_obj,total_list)\n",
    "        best_obj=[total_obj[k] for k in best_pop]\n",
    "'''----------result----------'''\n",
    "print(best_list)\n",
    "print(best_obj)\n",
    "print('the elapsed time:%s'% (time.time() - start_time))\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 取第一個解來畫排程甘特圖"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<iframe id=\"igraph\" scrolling=\"no\" style=\"border:none;\" seamless=\"seamless\" src=\"https://plot.ly/~ftcu5931/50.embed\" height=\"600px\" width=\"900px\"></iframe>"
      ],
      "text/plain": [
       "<plotly.tools.PlotlyDisplay object>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "'''--------plot gantt chart-------'''\n",
    "import pandas as pd\n",
    "import plotly.plotly as py\n",
    "import plotly.figure_factory as ff\n",
    "import datetime\n",
    "\n",
    "m_keys=[j+1 for j in range(num_mc)]\n",
    "j_keys=[j for j in range(num_job)]\n",
    "key_count={key:0 for key in j_keys}\n",
    "j_count={key:0 for key in j_keys}\n",
    "m_count={key:0 for key in m_keys}\n",
    "j_record={}\n",
    "for i in best_list[0]:\n",
    "    gen_t=int(pt[i][key_count[i]])\n",
    "    gen_m=int(ms[i][key_count[i]])\n",
    "    j_count[i]=j_count[i]+gen_t\n",
    "    m_count[gen_m]=m_count[gen_m]+gen_t\n",
    "    \n",
    "    if m_count[gen_m]<j_count[i]:\n",
    "        m_count[gen_m]=j_count[i]\n",
    "    elif m_count[gen_m]>j_count[i]:\n",
    "        j_count[i]=m_count[gen_m]\n",
    "    \n",
    "    start=j_count[i]-pt[i][key_count[i]]\n",
    "    start_time=str(datetime.timedelta(seconds=start)) # convert seconds to hours, minutes and seconds\n",
    "    end_time=str(datetime.timedelta(seconds=j_count[i]))  \n",
    "    j_record[(i,gen_m)]=[start_time,end_time]\n",
    "    \n",
    "    key_count[i]=key_count[i]+1\n",
    "        \n",
    "\n",
    "df=[]\n",
    "for m in m_keys:\n",
    "    for j in j_keys:\n",
    "        df.append(dict(Task='Machine %s'%(m), Start='2018-07-14 %s'%(str(j_record[(j,m)][0])), Finish='2018-07-14 %s'%(str(j_record[(j,m)][1])),Resource='Job %s'%(j+1)))\n",
    "    \n",
    "fig = ff.create_gantt(df, index_col='Resource', show_colorbar=True, group_tasks=True, showgrid_x=True, title='Job shop Schedule')\n",
    "py.iplot(fig, filename='GA_job_shop_scheduling1', world_readable=True)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
